ФОРМАЛЬНІ ГРАМАТИКИ. ЗВ'ЯЗОК ФОРМАЛЬНИХ ГРАМАТИК І СКІНЧЕННИХ АВТОМАТІВ

Інформація про навчальний заклад

ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
ТГВ
Кафедра:
Кафедра САПР

Інформація про роботу

Рік:
2010
Тип роботи:
Звіт до лабораторної роботи
Предмет:
Лiнгвiстичне забезпечення САПР

Частина тексту файла

МІНІСТЕРСТВО ОСВІТИ ТА НАУКИ УКРАЇНИ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА”  Кафедра САПР Звіт до Лабораторної роботи №3 на тему: «ФОРМАЛЬНІ ГРАМАТИКИ. ЗВ'ЯЗОК ФОРМАЛЬНИХ ГРАМАТИК І СКІНЧЕННИХ АВТОМАТІВ» З курсу «Лінгвістичне забезпечення САПР» 1. МЕТА РОБОТИ Ознайомлення з правилами побудови і застосування автоматів з магазинною пам’яттю. 2. КОРОТКІ ТЕОРЕТИЧНІ ВІДОМОСТІ Скінченні автомати можуть вирішувати тільки ті задачі, які потребують скінченного об’єму пам’яті. Але у компіляторах часто виникають задачі, які не можуть вирішуватися з такими обмеженнями. Наприклад, при обробці арифметичних виразів виникає задача перевірки балансу дужок, кількість лівих дужок повинна відповідати кількості правих. Кожна дужка у виразі має «свою роль», тому використання скінченного автомата для таких задач не прийнятне, оскільки множина станів може бути нескінченною. Для вирішення цієї та багатьох інших проблем компіляції, можуть використовуватись моделі потужніших автоматів. У них пам'ять скінченного автомата розширюється за рахунок додаткового механізму зберігання інформації. Один із методів – це використання магазину (або стека). Основна особливість магазинної пам’яті полягає в тому, що символи можна поміщати в магазин і видаляти їх з нього по одному. При цьому видаляється завжди тільки верхній символ, тобто символ, який був поміщений у магазин останнім. Коли інформація поміщається (записується) в магазин, кажуть, що вона «заштовхується», коли інформація видаляється з магазину – «виштовхується» з нього. Однією з моделей автомата, в яких використовується магазинний принцип організації пам’яті, є автомат з магазинною пам’яттю (скорочено МП-автомат). У ньому дуже просто поєднується пам'ять скінченного автомата і магазинна пам'ять. Як і у випадку скінченного автомата, обробка скінченного ланцюжка символів здійснюється за ряд простих кроків. На кожному кроці дії автомата конфігурація його пам’яті може змінюватись за рахунок: а) переходу у новий стан; б) заштовхування символу у магазин; в) виштовхування символу з магазину. Кожний крок обробки задається множиною правил, які використовують інформацію трьох видів: Стан; Верхній символ магазина; Біжучий вхідний символ. Залежно від отриманої інформації керуючий пристрій обирає або перехід в новий стан, або вихід з процесу. Перехід складається з трьох типів операцій: над станом, над магазином і над входом. Можливі такі операції: 1. Операції над магазином: Заштовхнути в магазин відповідний символ; Виштовхнути верхній символ з магазину; Залишити магазин без змін. 2. Операції над станом: Перейти в заданий стан. 3. Операції над входом: Перейти до наступного вхідного символу і зробити його поточним; Залишити цей вхідний символ поточним. МП-автомат визначається такими характеристиками:  де  – скінченна множина символів станів, які відображають усі можливі стани керуючого пристрою;  - скінченний вхідний алфавіт;  - скінченний алфавіт магазинних символів;  - керуюча функція, яка кожній комбінації вхідного символу, магазинного символу, стану ставить у відповідність перехід у відповідний стан або вихід;  - початковий стан керуючого пристрою;  - початковий символ, який є в магазині в початковий момент;  - множина прикінцевих станів. МП-автомат називається розпізнавачем, якщо у нього є два виходи: 1. ДОПУСТИТИ; 2. ВІДКИНУТИ. Ланцюжок символів вхідного алфавіту (включаючи кінцевий маркер) допускається розпізнавачем, якщо під дією цього ланцюжка автомат, який розпочав роботу у своєму початковому стані з початковим вмістом магазина, робить ряд переходів, які приводять до виходу «ДОПУСТИТИ». В протилежному випадку ланцюжок відкидається. При описанні переходів МП-автомата позначатимемо дії автомата словами: ЗАШТОВХНУТИ (А) – заштовхнути магазинний символ А у магазин; ВИШТОВХНУТИ – виштовхнути верхній символ з магазина; СТАН (S) – стан S; ЗСУВ – зсунути вхідну головку на один символ; ТРИМАТИ – тримати поточний вхідний символ до наступного кроку. 3. ВИКОНАННЯ РОБОТИ ІНДИВІДУАЛЬНЕ З...
Антиботан аватар за замовчуванням

17.07.2020 15:07

Коментарі

Ви не можете залишити коментар. Для цього, будь ласка, увійдіть або зареєструйтесь.

Завантаження файлу

Якщо Ви маєте на своєму комп'ютері файли, пов'язані з навчанням( розрахункові, лабораторні, практичні, контрольні роботи та інше...), і Вам не шкода ними поділитись - то скористайтесь формою для завантаження файлу, попередньо заархівувавши все в архів .rar або .zip розміром до 100мб, і до нього невдовзі отримають доступ студенти всієї України! Ви отримаєте грошову винагороду в кінці місяця, якщо станете одним з трьох переможців!
Стань активним учасником руху antibotan!
Поділись актуальною інформацією,
і отримай привілеї у користуванні архівом! Детальніше

Оголошення від адміністратора

Антиботан аватар за замовчуванням

пропонує роботу

Admin

26.02.2019 12:38

Привіт усім учасникам нашого порталу! Хороші новини - з‘явилась можливість кожному заробити на своїх знаннях та вміннях. Тепер Ви можете продавати свої роботи на сайті заробляючи кошти, рейтинг і довіру користувачів. Потрібно завантажити роботу, вказати ціну і додати один інформативний скріншот з деякими частинами виконаних завдань. Навіть одна якісна і всім необхідна робота може продатися сотні разів. «Головою заробляти» продуктивніше ніж руками! :-)

Новини